<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2493：Share the Cakes</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Share the Cakes</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Share the Cakes</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Share the Cakes                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Lunar Rose is a pure and kind girl who was born in a serene town on, with surprising coincidence, the Mid-autumn Festival that year. Therefore, on each of her birthday, she enjoys two cakes: for the birthday, and for the festival.<br />
&nbsp;&nbsp;This year, Lunar would like to share the cakes with Jaddy, her boyfriend, on the nice day, isn&rsquo;t it so romantic? What is the tragedy, Jaddy screwed up, again:<br />
&nbsp;&nbsp;When Lunar placed two cakes on the table, she wanted Jaddy to cut the cakes for her so that they can both have half of the moon cake and so do the birthday cake. But Jaddy, as a lazy and impetuous guy, he just used a knife to cut them together easily, hence although the two cakes had been cut into two pieces each, they were not really uniform. What was worth? Lunar is a pretty perfectionist and suddenly quite angry with Jaddy due to his arbitrariness. Finally, Lunar chose to leave him. Stupid Jaddy!<br />
&nbsp;&nbsp;Jaddy became extremely regretful and distressing. Lunar, a softhearted girl, does not have the heart to make him so painful so that she&rsquo;d like to give Jaddy a chance to do it again. However, she set a strict limit for this task: Jaddy can only use one cut to separate the two cakes into equivalent halves. Evil Ms. Rose!<br />
&nbsp;&nbsp;Both two cakes are convex polygons; the table and knife are both big enough and long enough thus can be considered as infinite planar and line. This way, tell Jaddy a strategy, which means a line, satisfying Lunar&rsquo;s condition to cut cakes so that he can get her back.</span></p>
<div class="panel_bottom"><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>输入格式</h3><p><div class="panel_content"><span style="font-size: medium">&nbsp;&nbsp;The first line of the input data is a positive integer T (T &lt;= 100) indicating the number of test cases. Then T cases follow. Each test case contains description of two cakes (polygons): each polygon begins with an integer n which denotes the number of vertices, and then n pairs of integers (x, y) follows describing the coordinates of vertices counterclockwise. You may assume that each polygon has no more than 20 vertices and all the coordinates are in range of [-1000, 1000]. Besides, the two polygons can be separated by a line, without touching on any points of the line.</span></div></p><hr/><h3>输出格式</h3><p><div class="panel_content"><span style="font-size: medium">&nbsp;&nbsp;For each test case, output two real numbers k and b, leading by the case number, which means that Jaddy should cut the cakes along the line y=k*x + b. It is guaranteed that both k and b among the answers are in range of [-10000, 10000]. See sample output for further details. Any answer with 10^-4 relative or absolute error is acceptable.</span></div>
<div class="panel_content">
<pre></pre>
</div></p><hr/><h3>样例输入</h3><pre>2
3
0 0
1 1
0 2
3
2 1
3 0
3 2
4
0 0
1 0
1 1
0 1
4
2 2
3 2
3 3
2 3
 
</pre><hr/><h3>样例输出</h3><pre>Case #1: 0 1
Case #2: 1 0
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Acm 2011 上海</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2493" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2493" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>